import time
import numpy as np


# 插入排序
def insert_sort(array):
    count = len(array)
    for x in range(1, count):
        index = x

        for i in range(index, 0, -1):
            temp = array[i]
            # print(arr[i], arr[i-1])
            if array[i] > array[i - 1]:
                array[i] = array[i - 1]
                array[i - 1] = temp


# 选择排序
def select_sort(array):
    count = len(array)

    for j in range(0, count):
        index = j
        max_ele = 0
        max_index = index
        for i in range(index, count):
            if array[i] > max_ele:
                max_ele = array[i]
                max_index = i

        temp = array[index]
        array[index] = max_ele
        array[max_index] = temp


# 冒泡排序
def bubble_sort(array):
    count = len(array)
    for i in range(0, count):
        for j in range(0, count - 1):
            if array[j] < array[j + 1]:
                temp = array[j]
                array[j] = array[j + 1]
                array[j + 1] = temp


# 快速排序 递归
def quicksort(array):
    if len(array) == 1 or len(array) == 0:
        return array
    if len(array) == 2:
        # print(array)
        if array[0] > array[1]:
            array[0], array[1] = array[1], array[0]
            return array
        # print(array)

    # print(array)
    pivot = array[int(len(array)/2)]
    array_left = []
    array_right = []
    for x in range(1, len(array)):
        if array[x] < pivot:

            array_left.append(array[x])
        else:

            array_right.append(array[x])

    # print("left", array_left)
    # print("righ", array_right)
    return quicksort(array_left) + [pivot] + quicksort(array_right)


if __name__ == '__main__':
    arr = np.arange(10000)
    np.random.shuffle(arr)
    # print(arr)
    start = time.process_time()
    insert_sort(arr)
    # print(arr)
    end = time.process_time()

    print('insert_sort is %6.3f' % (end - start))

    start = time.process_time()
    select_sort(arr)
    end = time.process_time()
    # print(arr)
    print('select_sort is %6.3f' % (end - start))

    start = time.process_time()
    bubble_sort(arr)
    end = time.process_time()
    # print(arr)
    print('bubble_sort is %6.3f' % (end - start))

    start = time.process_time()
    quicksort(arr)
    end = time.process_time()
    # print(arr)
    print('quicksort is %6.3f' % (end - start))

    # start = time.process_time()
    # arr.sort()
    # end = time.process_time()
    # # print(arr)
    # print('different is %6.3f' % (end - start))
